Best-time-buy-and-sell-stock --- leetcode 买卖股票问题

leetcode 刷题
  1. level 1
    1. 121. Best Time to Buy and Sell Stock
  2. level 2
    1. 122. Best Time to Buy and Sell Stock II
  3. level 3
    1. 122. Best Time to Buy and Sell Stock III
  4. level 4
    1. 188. Best Time to Buy and Sell Stock IV

level 1

121. Best Time to Buy and Sell Stock

这题是第一层，因为只能买卖一次，维护一个全局最小值和一个全局最大值就好，最后返回一个全局最优解即可。

####code[java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0)
            return 0;
        int minmoney = prices[0];
        int maxmonty = 0;
        for (int i = 1; i < prices.length; i++) {
            if(prices[i] - minmoney > 0) {
                if(prices[i] - minmoney > maxmonty)
                    maxmonty = prices[i] - minmoney;
            }
            if(prices[i] < minmoney)
                minmoney = prices[i];
        }
        return maxmonty;
    }
}

level 2

122. Best Time to Buy and Sell Stock II

这题也是比较简单的，因为可以随买随卖，所以只要后一天的价格比前一天的高，就卖就好，我觉得比 level I 还简单。

####code[java]

1
2
3
4
5
6
7
8
9
10
11

public class Solution {
    public int maxProfit(int[] prices) {
        int total = 0;
        for(int i = 0; i < prices.length - 1; i++) {
            if(prices[i+1] - prices[i] > 0)
                total += (prices[i+1] - prices[i]);
        }
        return total;
    }
}

level 3

122. Best Time to Buy and Sell Stock III

这题还是需要技巧的，因为只能够买卖两次，而且买另一个之前需要卖掉前一个。所以这题我们没办法只用O(1)的空间了。这题而且需要两个数组，一个数组表示前一个 stock 买卖的情况，另一个数组表示后一个 stock 买卖的情况。最后再遍历两个数组，求两个数组相加后最大 profit。

第一个数组就和 level I 一样，把当前的全局最优解放到对应下标的数组就好。

第二个数组注意下标，因为进行的第二次交易，所以我们要从后往前遍历，记录下全局最大的 price 和到当前坐标下的全局最优解。

最后遍历两个数组，每一个下标的结果都加起来即可。

####code[java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

/**
 * @author zhengyu
 * @date 2016年1月24日
 */
public class Solution {
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] test = {1,2,4};
        int[] test2 = {4,6,3,5,6,7,8,3,4,5,3,5,6,2,5,8};
        System.out.println(maxProfit(test));
        System.out.println(maxProfit(test2));
    }
    
    public static int maxProfit(int[] prices) {
        if(prices.length == 0)
            return 0;
        int len = prices.length;
        int[] first = new int[len];
        int[] second = new int[len];
        
        int minprofit = prices[0];
        int maxprofit = 0;
        for(int i = 1; i < len; i++) {
            maxprofit = Math.max(maxprofit, prices[i] - minprofit);
            first[i] = maxprofit;
            minprofit = Math.min(minprofit, prices[i]);
        }
        
        int maxprice = prices[len - 1];
        maxprofit = 0;
        int index = len - 2;
        for(int i = len - 2; i > -1; i--) {
            maxprofit = Math.max(maxprofit, maxprice - prices[i]);
            second[index--] = maxprofit;
            maxprice = Math.max(maxprice, prices[i]);
        }
        
        int result = 0;
        for(int i = 0; i < len; i++) 
            result = Math.max(first[i] + second[i], result);
        return result;
    }

}

level 4

188. Best Time to Buy and Sell Stock IV

这个应该是这个系列最难的题目了。还是前面的条件，但是这次能买卖多少次是用户自己输入的。